package 第2节数组;
//二分查找
public class BinarySearch {
    public static void main(String[] args) {
        //O(logN)
        int[] arr = {1,2,3,4,5,6,7,8,9};
        int key = 10;
        int low = 0;
        int high = arr.length - 1;
        int mid = (low + high) / 2;
        while (arr[mid] != key) {
            if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            if (high < low) {
                mid = -1;
                break;
            }
            mid = (low + high) / 2;
        }
        System.out.println(mid);
    }
}
